#ifndef _LAB1_H_
#define  _LAB1_H_
#include <stdlib.h>
#include <stdio.h> 



//存放多项式某项的结点结构 
struct node
{
  int exp ;  // 表示指数
  int coef ; //表示系数
  struct node *next;  //指向下一个结点的指针 
};

typedef  struct node * PNODE ;

/*
  函数功能：生成多项式
  函数名：createPoly
  函数参数：无
  返回值：指向多项式的头指针 
*/
PNODE createPoly(void)
{
    //在此处填写代码，能实现创建一个多项式并返回多项式头指针的函数
	//注意：头指针不存放多项式的项。 
    /**********  Begin **********/
 	PNODE head = (PNODE)malloc(sizeof(struct node));
 	PNODE tail = head;
 	int coef, exp;
    if (NULL == head) {
        printf("Out of Space\n");
        return NULL;
    }
    head->next = NULL;
    head->coef = 0;
    head->exp = 0;
    while (1) {
        scanf("%d %d", &coef, &exp);
        if (0 == coef)
            break;
        PNODE p = (PNODE)malloc(sizeof(struct node));
        if (NULL == p) {
            printf("Out of Space\n");
            return NULL;
        }
        p->exp = exp;
        p->coef = coef;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    return head;
    /**********  End  **********/
} 
  
/*
   函数功能：进行多项式相加
   函数名：addPoly
   函数参数：polyAddLeft ：加法左边多项式头指针, polyAddRight：加法右边多项式头指针 
   返回值：指向结果多项式的头指针 
*/
PNODE addPoly(PNODE polyAddLeft , PNODE polyAddRight)
{
    //在此处填写代码，能实现创两个多项式相加并返回结果多项式头指针的函数
    /**********  Begin **********/
    // 初始化链表
    int coef = 0;
    PNODE pl = polyAddLeft->next, pr = polyAddRight->next;
    PNODE tail = NULL;
    PNODE polySum = (PNODE)malloc(sizeof(struct node));
    if (NULL == polySum) {
        printf("Out of Space\n");
        return NULL;
    }
    polySum->exp = 0;
    polySum->coef = 0;
    polySum->next = NULL;
    tail = polySum;
    // 开始相加
    for (int i; 1; ++i) {
        coef = 0;
        if (NULL != pl) {
            if (pl->exp == i) {
                coef += pl->coef;
                pl = pl->next;
            }
        }
        if (NULL != pr) {
            if (pr->exp == i) {
                coef += pr->coef;
                pr = pr->next;
            }
        }
        if (0 != coef) {
            PNODE nodeSum = (PNODE)malloc(sizeof(struct node));
            if (NULL == nodeSum) {
                printf("Out of Space\n");
                return NULL;
            }
            nodeSum->exp = i;
            nodeSum->coef = coef;
            nodeSum->next = NULL;
            tail->next = nodeSum;
            tail = nodeSum;
        }
        if (NULL == pl && NULL == pr) {
            break;
        }
    }
    return polySum;
    /**********  End **********/
}  
  
/*
   函数功能：输出多项式 
   函数名：printPoly
   函数参数：待输出多项式的头指针poly 
   返回值：无 
*/
 void printPoly(PNODE poly)
 {
 	//在此处填写代码，能实现按格式输出多项式的功能，输出格式样例见说明 
    /**********  Begin **********/
    PNODE p;
 	for (p = poly->next; NULL != p; p = p->next) {
 	    if (p->coef >= 0 && p != poly->next) {
 	        printf("+");
 	    }
        printf("%dx^%d", p->coef, p->exp);
 	}
    
    /**********  End **********/
}  

void destroyPoly(PNODE poly)
{
//释放存储多项式的链表空间
    PNODE pre = poly, post = poly;
    while (pre != NULL) {
        post = pre->next;
        free(pre);
        pre = NULL;
        pre = post;
    }
}
#endif
